package Leetcode.数组字符串;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @ClassName 股票价格跨度
 * @since: 2023/8/28 16:13
 * @auth: kirito
 * @description:
 * 设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
 *
 * 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 *
 * 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。
 *
 * 实现 StockSpanner 类：
 *
 * StockSpanner() 初始化类对象。
 * int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。
 *
 *
 * 示例：
 *
 * 输入：
 * ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
 * [[], [100], [80], [60], [70], [60], [75], [85]]
 * 输出：
 * [null, 1, 1, 1, 2, 1, 4, 6]
 *
 * 解释：
 * StockSpanner stockSpanner = new StockSpanner();
 * stockSpanner.next(100); // 返回 1
 * stockSpanner.next(80);  // 返回 1
 * stockSpanner.next(60);  // 返回 1
 * stockSpanner.next(70);  // 返回 2
 * stockSpanner.next(60);  // 返回 1
 * stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
 * stockSpanner.next(85);  // 返回 6
 *
 * 文字游戏。。。。。。。。
 * 说人话就是  找当前索引前的第一个比他的值的索引，然后相减就是跨度。。
 **/
public class 股票价格跨度 {
    static int N = 10010, len = 100, idx = 0;
    static int[] nums = new int[N], region = new int[N / len + 10];
//    public StockSpanner() {
//        for (int i = 0; i <= getIdx(idx); i++) region[i] = 0;
//        idx = 0;
//    }
    int getIdx(int x) {
        return (x - 1) / len + 1;
    }
    Deque<int[]> d = new ArrayDeque<>();
    int cur = 0;
    public int next(int price) {
        while (!d.isEmpty() && d.peekLast()[1] <= price) d.pollLast();
        int prev = d.isEmpty() ? -1 : d.peekLast()[0], ans = cur - prev;
        d.addLast(new int[]{cur++, price});
        return ans;
    }

}
